package leetcode.list;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by zxc on 2018/10/3.
 */
public class DeepCopyList {

    static class RandomListNode {
        int val;
        RandomListNode next, random;
        RandomListNode(int x){
             this.val = x;
        }
    }

    /*https://blog.csdn.net/jinhuoxingkong/article/details/70791923  random复制有错
      （1）新建一个链表的头结点，建立以HashMap，将新老结点以键值对的方式存储在Map中
      （2）然后遍历原来链表，根据它复制新的结点，也是以键值对的方式存储在Map中
      （3）最后再从头遍历，将Random的指针进行赋值，注意random指针必须得在链表建立的基础之上才可以，
      要不没办法指向Random的指向拷贝以Map的形式可能不好理解，其实random也就是next.next...的形式，
      也是复制的next，这样就理解了
 */
    private static RandomListNode copyRandomList(RandomListNode head) {
        if(head == null){
            return head;
        }
        int numberId = 2;
        //新建一个链表的头结点
        RandomListNode newHead = new RandomListNode(head.val);
        RandomListNode oldp = head.next;
        RandomListNode newp=newHead;
        Map<RandomListNode,Integer> mapOld = new HashMap<RandomListNode,Integer>();
        Map<Integer,RandomListNode> mapNew = new HashMap<Integer,RandomListNode>();
        mapOld.put(head, 1);
        mapNew.put(1, newp);

        //对旧链表进行复制
        while(oldp != null){
            RandomListNode temp = new RandomListNode(oldp.val);
            mapOld.put(oldp, numberId);
            mapNew.put(numberId, temp);
            newp.next = temp;
            newp = newp.next;
            oldp = oldp.next;
            numberId++;
        }

        //将Random指针进行复制
        newp = newHead;
        oldp = head;
        while(newp != null){
            //这里的random指针相当于有几个next比较好理解
            if(oldp.random != null){
                newp.random = mapNew.get(mapOld.get(oldp.random));
            }
            newp = newp.next;
            oldp = oldp.next;
        }
        return newHead;
    }



    public static void main(String[] args) {
        RandomListNode node1 = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);
        RandomListNode node4 = new RandomListNode(4);
        RandomListNode node5 = new RandomListNode(5);
        RandomListNode node6 = new RandomListNode(6);
        RandomListNode node7 = new RandomListNode(7);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        node7.next=null;
        node1.random = node3;
        RandomListNode  headA = node1;

        System.out.println("Before Copy:");
        System.out.print("headA:");
        while (headA!=null){
            System.out.print(headA.val+">");
            headA = headA.next;
        }
        System.out.println("end");

        /*深拷贝*/
        RandomListNode newHead = copyRandomList(node1);

        if(newHead != null) {
            System.out.println("After Copy:");
            System.out.print("headA:");
            while (newHead!=null){
                System.out.print(newHead.val+">");
                newHead = newHead.next;
            }
            System.out.println("end");
        }else{
            System.out.println("无深拷贝链表" );
        }
        System.out.println("end");
    }
}
